Dynamic Programming

The core thought of DP is that, if a question can be divided into sub-questions, and each sub-questions can use the answer of last one, then, to solve the final question, we just need to get the answer of the most rent sub-question.

For example, if I want to measure the distance between A and B. And if there’s a milestone in C, saying that the distance from B and C is 100 km, them I just need to measure the distance from A and C, and simply plus the result with 100. When we using DP, there will be lots of “C”.

In algorithm questions, the key feature is that if we can make question divided, and this usually happens in 2D-array, for instance, like 2D graph question or comparing two strings.

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• The input strings consist of lowercase English characters only.

In such scenario, we usually set an 2D matrix as the ‘milestone’, and usually name it as dp

the key is : dp(i,j) means the longest common subsequence of text1[:i] and text2[:j]. If text1[i]==text2[j], then dp(i,j) should equal dp(i-1,j-1)+1 Otherwise, dp(i,j)=max(dp(i-1,j), dp(i,j-1))

**Solution **

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n=len(text1)
        m=len(text2)
        dp=[[0]*(m+1) for i in range(n+1)]
        for i in range(n):
            for j in range(m):
                if text1[i]==text2[j]:
                    #create generator
                    dp[i+1][j+1]=dp[i][j]+1
                else:
                    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
        print(dp)
        return dp[-1][-1]

221. Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

Solution

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                matrix[i][j]=int(matrix[i][j])
                if matrix[i][j] and i and j:
                    matrix[i][j]=min(matrix[i-1][j],matrix[i][j-1],matrix[i-1][j-1])+1
        return len(matrix) and max(map(max,matrix)) **2

If we overwatch the change of dp matrix, we will find interesting result.